
package main.new_2024.month_02;


import main.dataStruct.TreeNode;

import java.util.*;

/**
 * @Description: todo 938. 二叉搜索树的范围和
 * 给定二叉搜索树的根结点 root，返回值位于范围 [low, high] 之间的所有结点的值的和。
 * @Author: Take-off
 * @Date: 1:00 PM 2023/6/
 * @Param:
 * @return:
 **/
public class Solution0226 {

    //二叉搜索树的范围和 : 适用二叉搜索树左边节点 < 根节点 < 右边节点 的特性
    public int rangeSumBST(TreeNode root, int low, int high) {
        Queue<TreeNode> stack = new LinkedList<>();
        int sum = 0;
        sum = add(stack,sum,root,low,high);
        while (!stack.isEmpty()){
            sum = add(stack,sum,stack.poll(),low,high);
        }
        return sum;
    }

    public int add(Queue<TreeNode> stack,int sum ,TreeNode root, int low, int high){
        if (root.val < low ){
            if (root.right != null){
                stack.add(root.right);
            }
        }else if(root.val > high ){
            if (root.left != null){
                stack.add(root.left);
            }
        }else {
            sum = sum + root.val;
            if (root.right != null){
                stack.add(root.right);
            }
            if (root.left != null){
                stack.add(root.left);
            }
        }
        return sum;
    }

    public static void main(String[] args) {
        TreeNode one = new TreeNode(6);
        TreeNode two = new TreeNode(15);
        TreeNode root = new TreeNode(10,one,two);
        Solution0226 test = new Solution0226();
        test.rangeSumBST(root,6,10);
    }

}

